home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / SCIENCE / NTUMIN10.ZIP / CAMPB.C < prev    next >
C/C++ Source or Header  |  1992-03-09  |  12KB  |  338 lines
  1. /****************************************************************************
  2.  *
  3.  *      Program name : CAMPB.C
  4.  *
  5.  *      This is the actual minimization algorithm. Variation from the actual
  6.  *    CAMP algorithm is as follows:
  7.  *        1.    Minterms with adjacency 0 or 1 is minimised first
  8.  *        2.    Select next minterm in increasing order of adjacency
  9.  *        3.    To shrink the CPT, select an adjacent term, mi that has the
  10.  *            largest wi AND is already covered
  11.  *
  12.  * --------------------------------------------------------------------------
  13.  *    Copyright (c) 1992. All Rights Reserved. Nanyang Technological
  14.  *    University.
  15.  *
  16.  *    You are free to use, copy and distribute this software and its
  17.  *    documentation providing that:
  18.  *
  19.  *        NO FEE IS CHARGED FOR USE, COPYING OR DISTRIBUTION.
  20.  *
  21.  *        IT IS NOT MODIFIED IN ANY WAY.
  22.  *
  23.  *        THE COPYRIGHT NOTICE APPEAR IN ALL COPIES.
  24.  *
  25.  *    This program is provided "AS IS" without any warranty, expressed or
  26.  *    implied, including but not limited to fitness for any particular
  27.  *    purpose.
  28.  *
  29.  *    If you find NTUMIN fast, easy, and useful, a note or comment would be
  30.  *    appreciated. Please send to:
  31.  *
  32.  *        Boon-Tiong Tan or Othman Bin Ahmad
  33.  *        School of EEE
  34.  *        Nanyang Technological University
  35.  *        Nanyang Avenue
  36.  *        Singapore 2263
  37.  *        Republic of Singapore
  38.  *
  39.  ***************************************************************************/
  40.  
  41. #include <stdio.h>
  42. #include <stdlib.h>
  43. #include <string.h>
  44. #define mask8 255
  45.  
  46. unsigned char   *campb(a, b)              /* pointer to a & b array passed */
  47. unsigned char   *a, *b;
  48.  
  49. {
  50.    unsigned short   pterm, ma, mb, *pm, pos;
  51.    unsigned  long   m, k, topow();
  52.    register  long   i, wo, wi;
  53.    register  char   j;
  54.          char   test;
  55.    unsigned  char   *c, *d, *e, *s, *temp, count, limit, adj0, adji;
  56.    unsigned  char   n, adj, adjacency(), nspm, cover;
  57.    unsigned  char   *adjacent(), *reduce(), *cpt(), *ssm(), adj_of_mi();
  58.  
  59.  
  60.    mb = *(b+2)<<8 | *(b+1);            /* no. of minterms in b-array */
  61.  
  62.    n    = *a;                          /* no. of variables */
  63.    nspm = *(a+3);                      /* no. of bytes/minterm */
  64.    ma = *(a+2)<<8 | *(a+1);            /* no. of minterms in a-array */
  65.  
  66.    temp = (unsigned char *) malloc(nspm+1);        /* temporary storage */
  67.    if (temp == 0)
  68.       {
  69.      printf("Out of memory -- CAMPB, *temp\n");
  70.      printf("Program terminated - 1\n");
  71.      exit(0);
  72.       }
  73.  
  74.    s = (unsigned char *) malloc(4);                /* header of s-array */
  75.    if (s == 0)
  76.       {
  77.      printf("Out of memory -- CAMPB, *s\n");
  78.      printf("Program terminated - 2\n");
  79.      exit(0);
  80.       }
  81.  
  82.    pterm = 0;                                /* no. of product term */
  83.  
  84.    /***
  85.     ***  MINIMIZE ALL MINTERMS WITH ADJACENCY OF 0 & 1 FIRST
  86.     ***/
  87.  
  88.    for (i=0; i<mb; i++)                      /* for adj = 0 or 1 */
  89.       {
  90.      *b = n;                             /* assign back to n */
  91.  
  92.      memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  93.      c = adjacent(temp, a, 1);           /* obtain the adjacent terms */
  94.      adj = *(c+1);                       /* adjacency of minterm */
  95.  
  96.      if (adj <= 1)                       /* adjacency 0 or 1 */
  97.         {
  98.            d = cpt(c);                   /* generate CPT */
  99.  
  100.            s = (unsigned char *) realloc(s,4+n*(pterm+1));   /* more space */
  101.            if (s == 0)
  102.           {
  103.              printf("Out of memory -- CAMPB, *s\n");
  104.              printf("Program terminated - 3\n");
  105.              exit(0);
  106.           }
  107.            memcpy ((s+4+n*pterm),d,n);   /* add CPT to soln array */
  108.            pterm++;                      /* product term count */
  109.  
  110.            b = reduce(c,b,i);            /* remove minterms covered from b-array */
  111.            i = (char) *b;                /* index pointer of b-array */
  112.            mb = *(b+2)<<8 | *(b+1);      /* value of mb altered in b-array */
  113.  
  114.            free(d);                    /* free pointer */
  115.         }
  116.      free(c);                            /* free pointer */
  117.       }
  118.  
  119.    /***
  120.     ***  MINIMIZE MINTERMS WITH INCREASING ADJACENCY GREATER THAN 1
  121.     ***/
  122.  
  123.    limit = 2;                               /* next adjacency limit */
  124.  
  125.    while (mb > 0)                           /* not all minterms covered */
  126.       {
  127.      for (i=0; i<mb; i++)               /* remaining minterms in b-array */
  128.         {
  129.            *b = n;                      /* assign back to n */
  130.  
  131.            memcpy(temp, (b+4+nspm*i), nspm);   /* pick a minterm from b-array */
  132.            c = adjacent(temp, a, limit);       /* obtain the adjacent terms */
  133.            adj = *(c+1);                       /* adjacency of minterm */
  134.  
  135.            if (adj == limit)                   /* next adjacency limit */
  136.           {
  137.              /***
  138.               ***  GENERATE SSM AND TEST FOR COVERAGE BY FUNCTION
  139.               ***/
  140.  
  141.              d = cpt(c);                   /* generate CPT */
  142.              e = ssm(d);                   /* generate SSM */
  143.              m = topow(*(e+1));            /* no. of SSM terms */
  144.  
  145.              for (j=0; j<m; j++)            /* check for SSM coverage */
  146.             {
  147.                memcpy (temp, (e+4+nspm*j), nspm);  /* pick SSM term */
  148.                test = exist (temp, a, ma);
  149.                if (test == -1)           /* SSM term not in a-array */
  150.                   break;
  151.             }
  152.  
  153.              /***
  154.               ***  ALL SSM COVERED BY THE FUNCTION, SELECT CPT AS PRODUCT TERM
  155.               ***/
  156.  
  157.              if (test == 0)                 /* all SSM's covered by fn */
  158.             {
  159.                if (m > 65536)                  /* too many SSM terms */
  160.                   {
  161.                  printf("Product Term Too Huge \n");
  162.                  printf("Program terminated \n");
  163.                  exit(0);
  164.                   }
  165.                *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  166.                *(e+2) = (m-1)>>8 & mask8;
  167.                b = reduce(e,b,i);        /* remove minterms covered from b-array */
  168.                i = (char) *b;            /* update pointer to b-array */
  169.                mb = *(b+2)<<8 | *(b+1);  /* no. of minterms in b-array */
  170.  
  171.                s = (unsigned char *) realloc(s, 4+n*(pterm+1)); /* more space */
  172.                if (s == 0)
  173.                   {
  174.                  printf("Out of memory -- CAMPB, *s\n");
  175.                  printf("Program terminated - 4\n");
  176.                  exit(0);
  177.                   }
  178.                memcpy((s+4+n*pterm),d,n);     /* add CPT to soln array */
  179.                pterm++;                       /* no. of product terms */
  180.  
  181.                free(d);                       /* free pointers */
  182.                free(e);
  183.             }
  184.              else
  185.             {
  186.                /***
  187.                 ***  SSM NOT COVERED BY THE FUNCTION
  188.                 ***/
  189.  
  190.                free(d);                       /* free pointer */
  191.                cover =0;                      /* coverage status */
  192.  
  193.                while (!cover)        /* do until shrinked SSM is covered */
  194.                   {
  195.                  /***
  196.                   ***  OBTAIN AN ARRAY, PM OF POSITIONS OF ADJACENT TERMS,
  197.                   ***  MI WITH THE LARGEST WI
  198.                   ***/
  199.  
  200.                  wo = -1;                        /* initial value */
  201.                  for (j=0; j<adj; j++)           /* do for all adjacent terms */
  202.                     {
  203.                        memcpy(temp,(c+4+nspm*(j+1)),nspm); /* pick adjacent term */
  204.  
  205.                        wi = adj_of_mi(temp,e,a);           /* obtain wi */
  206.                        if (wi>wo)
  207.                       {
  208.                          if (wo != -1)                 /* not the first */
  209.                         free(pm);
  210.                          wo = wi;                      /* new lowest value */
  211.                          count = 1;                    /* reset count to 1 */
  212.  
  213.                          pm = (unsigned short *) malloc(2);  /* space for pm */
  214.                          if (pm==0)
  215.                         {
  216.                            printf("Out of memory -- CAMPB, *pm\n");
  217.                            printf("Program terminated - 5\n");
  218.                            exit(0);
  219.                         }
  220.                          *pm = j;                      /* first element */
  221.                       }
  222.                        else if (wi==wo)                    /* wi as large */
  223.                       {
  224.                          count++;                      /* no. of element in pm-array */
  225.  
  226.                          pm = (unsigned short *) realloc (pm, 2*count);  /* more space */
  227.                          if (pm==0)
  228.                         {
  229.                            printf("Out of memory -- CAMPB, *pm\n");
  230.                            printf("Program terminated - 6\n");
  231.                            exit(0);
  232.                         }
  233.                          *(pm+count-1) = j;            /* elements of pm-array */
  234.                       }
  235.                     }
  236.                  free(e);
  237.  
  238.                  /***
  239.                   ***  SELECT FROM PM-ARRAY, AN ADJACENT TERM THAT HAS ALREADY BEEN COVERED
  240.                   ***/
  241.  
  242.                  for (j=0; j<count; j++)              /* do for all element in pm-array */
  243.                     {
  244.                        memcpy(temp, (c+4+nspm*(1+ *(pm+j))), nspm);    /* pick adj term */
  245.                        test = exist(temp,b,mb);
  246.                        if (test == -1)                               /* already covered */
  247.                       break;
  248.                     }
  249.  
  250.                  if (j==count)                     /* select the 1st if all not covered */
  251.                     j = 0;
  252.  
  253.                  adj--;                            /* no. of adj terms in c-array */
  254.                  *(c+1) = adj;                     /* adjacency after shrinking CPT */
  255.                  pos = *(pm+j);                    /* required position of adj term */
  256.  
  257.                  free(pm);                         /* free pointer */
  258.  
  259.                  /***
  260.                   ***  SHRINK CPT (REMOVE 1 ADJACENT TERM FROM C-ARRAY), GENERATE NEW CPT, SSM
  261.                   ***  AND TEST FOR COVERAGE BY FUNCTION
  262.                   ***/
  263.  
  264.                  memcpy((c+4+nspm*(1+pos)), (c+4+nspm*(2+pos)), nspm*(adj-pos));  /* shrink CPT */
  265.  
  266.                  c = (unsigned char*) realloc(c, 4+nspm*(1+adj));   /* reduce space */
  267.                  if (c==0)
  268.                     {
  269.                        printf("Out of memory -- CAMPC, *c\n");
  270.                        printf("Program terminated - 7\n");
  271.                        exit(0);
  272.                     }
  273.  
  274.                  d = cpt(c);                  /* generate CPT */
  275.                  e = ssm(d);                  /* generate SSM */
  276.                  m = topow(*(e+1));           /* no. of SSM terms */
  277.  
  278.                  for (k=0; k<m; k++)          /* check SSM coverage by function */
  279.                     {
  280.                        memcpy(temp, (e+4+nspm*k), nspm);  /* pick SSM term */
  281.                        test = exist(temp,a,ma);
  282.                        if (test == -1)                    /* SSM term not covered */
  283.                       break;
  284.                     }
  285.  
  286.                  /***
  287.                   ***  SHRINKED SSM COVERED BY FUNCTION, REDUCE B-ARRAY
  288.                   ***  AND SELECT SHRINKED CPT AS PRODUCT TERM
  289.                   ***/
  290.  
  291.                  if (test==0)                   /* SSM covered */
  292.                     {
  293.                        if (m > 65536)                  /* too many SSM terms */
  294.                       {
  295.                          printf("Product Term Too Huge \n");
  296.                          printf("Program terminated \n");
  297.                          exit(0);
  298.                       }
  299.                        *(e+1) = (m-1) & mask8;         /* no. of SSM terms minus 1 */
  300.                        *(e+2) = (m-1)>>8 & mask8;
  301.                        b = reduce(e, b, i);     /* remove minterms covered from b-array */
  302.                        i = (char) *b;           /* update pointer to b-array */
  303.                        mb = *(b+2)<<8 | *(b+1); /* no. of minterms in b-array */
  304.  
  305.                        s = (unsigned char *) realloc(s, 4+n*(pterm+1));  /* more space */
  306.                        if (s==0)
  307.                       {
  308.                          printf("Out of memory -- CAMPC, *s\n");
  309.                          printf("Program terminated - 8\n");
  310.                          exit(0);
  311.                       }
  312.                        memcpy ((s+4+n*pterm), d, n);      /* add shrinked CPT to soln array */
  313.                        pterm++;                           /* no. of product terms */
  314.  
  315.                        cover = 1;                         /* coverage status */
  316.                        free(e);                           /* free pointer */
  317.                     }
  318.                  free (d);                      /* free pointer */
  319.                   }
  320.             }
  321.           }
  322.            free(c);                     /* free pointer */
  323.         }
  324.      limit++;
  325.       }
  326.    *s = n;                           /* no. of variables */
  327.    *(s+1) = pterm & mask8;           /* no. of product terms in 2 bytes */
  328.    *(s+2) = pterm>>8 & mask8;
  329.  
  330.    free(temp);                       /* free pointer */
  331.    free(a);
  332.    free(b);
  333.  
  334.    return(s);                        /* return solution array */
  335. }
  336.  
  337.  
  338.